/*
 * Copyright (C), 2015-2018
 * FileName: Solution136
 * Author:   zhao
 * Date:     2018/9/11 15:11
 * Description: 136. 只出现一次的数字
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredtwo;

import com.lizhaoblog.hundredone.CommonValue;

/**
 * 〈一句话功能简述〉<br>
 * 〈136. 只出现一次的数字〉
 *
 * @author zhao
 * @date 2018/9/11 15:11
 * @since 1.0.1
 */
public class Solution136 {
  /**************************************
   * 题目

   给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

   说明：

   你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

   示例 1:

   输入: [2,2,1]
   输出: 1
   示例 2:

   输入: [4,1,2,1,2]
   输出: 4
   **************************************/

  /**************************************
   *
   * 想法：
   *    分别加减，行不通
   *    多创建一个数组、无法达成
   * 我的做法
   *     没做出来，失败
   * 代码执行过程：
   *  输入，2, 3, 4, 2, 4
   *        2:0010
   *        3:0011
   *        4:0100
   *
   *  循环体：
   *    过程1：0001
   *    过程2：0101
   *    过程3：0011
   *    过程4：0011 = 3
   *
   * 总结：
   *    当要求空间复杂度的时候，可以考虑使用位运算
   *    异或运算符：a^b情况10,01为true，11,00为false
   *    下面步骤的循环
   *
   * ***********************************/
  public int singleNumber(int[] nums) {
    if (CommonValue.NOT_ANSWER) {

    }

    if (nums.length == 0) {
      return 0;
    }

    int result = nums[0];
    for (int i = 1; i < nums.length; i++) {
      // 异或运算符，
      // a^b情况10,01为true，11,00为false
      result ^= nums[i];
    }

    return result;
  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public void better() {
  }

}
